Back تحويل فورييه السريع Arabic Sürətli Furye çevirməsi Azerbaijani Transformada ràpida de Fourier Catalan Rychlá Fourierova transformace Czech Fast Fourier Transform Danish Schnelle Fourier-Transformation German Fast Fourier transform English Transformada rápida de Fourier Spanish تبدیل فوریه سریع Persian Transformation de Fourier rapide French

Fourier' kiirteisendus

Fourier' kiirteisenduse algoritmi keerukuse O(N log N (punane kõver) ja diskreetse Fourier' teisenduse keerukuse O(N²) (sinine kõver) võrdlus

Fourier' kiirteisendus (lühend FFT inglise keele sõnadest Fast Fourier Transform) on algoritmide kogum diskreetse Fourier' teisenduse (DFT) või selle pöördtehte (IDFT) kiireks sooritamiseks.

Fourier' teisendus on vajalik mitmetel aladel, et käsitleda signaali sagedusruumis. Selle arvutamine on definitsiooni järgi aga tingituna suurest keerukusest O(N²), kus N on signaali punktide arv, aeganõudev ning tihtipeale ebapraktiline.[1] Fourier’ kiirteisendus vähendab keerukust O(N log N) peale.[1]

Algoritmil oli murranguline mõju digitaalsignaalide töötlemise meetoditele – see on tänapäevani kasutusel inseneriteaduses, muusikatööstuses, matemaatikas jne. Populaarseks sai kiirteisenduse kasutamine 1965. aastal, kuid sarnase sisuga algoritme uurisid matemaatikud juba 19. sajandi alguses.[1]

  1. ↑ 1,0 1,1 1,2 Michael T. Heideman, Don H. Johnson, C. Sidney Burrus (oktoober 1984). "Gauss and the History of the Fast Fourier Transform" (PDF). IEEE ASSP Magazine. Vaadatud 30.05.2020.{{netiviide}}: CS1 hooldus: mitu nime: autorite loend (link)

Developed by StudentB